{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Absolute Sum Difference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #ordered-set #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #有序集合 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minAbsoluteSumDiff"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #绝对差值和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个正整数数组 <code>nums1</code> 和 <code>nums2</code> ，数组的长度都是 <code>n</code> 。</p>\n",
    "\n",
    "<p>数组 <code>nums1</code> 和 <code>nums2</code> 的 <strong>绝对差值和</strong> 定义为所有 <code>|nums1[i] - nums2[i]|</code>（<code>0 <= i < n</code>）的 <strong>总和</strong>（<strong>下标从 0 开始</strong>）。</p>\n",
    "\n",
    "<p>你可以选用 <code>nums1</code> 中的 <strong>任意一个</strong> 元素来替换 <code>nums1</code> 中的 <strong>至多</strong> 一个元素，以 <strong>最小化</strong> 绝对差值和。</p>\n",
    "\n",
    "<p>在替换数组 <code>nums1</code> 中最多一个元素 <strong>之后</strong> ，返回最小绝对差值和。因为答案可能很大，所以需要对 <code>10<sup>9</sup> + 7</code> <strong>取余 </strong>后返回。</p>\n",
    "\n",
    "<p><code>|x|</code> 定义为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>x >= 0</code> ，值为 <code>x</code> ，或者</li>\n",
    "\t<li>如果 <code>x <= 0</code> ，值为 <code>-x</code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [1,7,5], nums2 = [2,3,5]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>有两种可能的最优方案：\n",
    "- 将第二个元素替换为第一个元素：[1,<strong>7</strong>,5] => [1,<strong>1</strong>,5] ，或者\n",
    "- 将第二个元素替换为第三个元素：[1,<strong>7</strong>,5] => [1,<strong>5</strong>,5]\n",
    "两种方案的绝对差值和都是 <code>|1-2| + (|1-3| 或者 |5-3|) + |5-5| = </code>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>nums1 和 nums2 相等，所以不用替换元素。绝对差值和为 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3</strong><strong>：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]\n",
    "<strong>输出：</strong>20\n",
    "<strong>解释：</strong>将第一个元素替换为第二个元素：[<strong>1</strong>,10,4,4,2,7] => [<strong>10</strong>,10,4,4,2,7]\n",
    "绝对差值和为 <code>|10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20</code>\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length</code></li>\n",
    "\t<li><code>n == nums2.length</code></li>\n",
    "\t<li><code>1 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= nums1[i], nums2[i] <= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-absolute-sum-difference](https://leetcode.cn/problems/minimum-absolute-sum-difference/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-absolute-sum-difference](https://leetcode.cn/problems/minimum-absolute-sum-difference/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,7,5]\\n[2,3,5]', '[2,4,6,8,10]\\n[2,4,6,8,10]', '[1,10,4,4,2,7]\\n[9,3,5,1,7,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n, record, s, cur, MOD = len(nums1), sorted(nums1), 0, 0, 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            s += (diff := abs(nums1[i] - nums2[i]))\n",
    "            j = bisect_left(record, nums2[i])\n",
    "            if j < n:\n",
    "                cur = max(cur, diff - (record[j] - nums2[i]))\n",
    "            if j:\n",
    "                cur = max(cur, diff - (nums2[i] - record[j - 1]))\n",
    "        return (s - cur + MOD) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums3 = nums1[:]\n",
    "        nums3.sort()\n",
    "        n, max_diff = len(nums1), 0\n",
    "        total = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            t = abs(x-y)\n",
    "            total += t\n",
    "            i = bisect.bisect_left(nums3, y)\n",
    "            if i > 0:\n",
    "                max_diff = max(max_diff, t - abs(nums3[i-1]-y))\n",
    "            if i < n:\n",
    "                max_diff = max(max_diff, t - abs(nums3[i] - y ))\n",
    "        return (total - max_diff) % int(1e9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\r\n",
    "        tot = sum(abs(x - y) for x, y in zip(nums1, nums2))\r\n",
    "        n = len(nums1)\r\n",
    "        a = sorted(nums1)\r\n",
    "        res = tot\r\n",
    "        for i in range(n):\r\n",
    "            x = nums1[i] \r\n",
    "            y = nums2[i]\r\n",
    "            j = bisect_left(a, y)\r\n",
    "            if j < n:\r\n",
    "                res = min(res, tot - abs(x - y) + a[j] - y)\r\n",
    "            if j :\r\n",
    "                res = min(res, tot - abs(x - y) + y - a[j - 1])\r\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        s = nums1.copy()\n",
    "        s.sort()\n",
    "        l = len(nums1)\n",
    "        ret, m = 0, 10 ** 9 + 7\n",
    "        r = 0\n",
    "        for a, b in zip(nums1, nums2):\n",
    "            t = abs(a - b)\n",
    "            ret += t\n",
    "            if t > r:\n",
    "                pl = min(l - 1, bisect.bisect_left(s, b))\n",
    "                na = s[pl]\n",
    "                # print(f\"find na {na} {s[pl - 1]} for {a}=>B {b}\")\n",
    "                nt = abs(na - b)\n",
    "                if pl - 1 >= 0:\n",
    "                    nt = min(nt, abs(s[pl - 1] - b))\n",
    "                r = max(r, t - nt)\n",
    "        # print(f\"ret {ret} {r}\")\n",
    "        return (ret - r) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        s = 0\n",
    "        mod = 10**9+7\n",
    "        for i in range(len(nums1)):\n",
    "            s += abs(nums1[i]-nums2[i])\n",
    "           # s = s%m\n",
    "\n",
    "        a = sorted(nums1)\n",
    "        tmp = s\n",
    "        for i in range(len(nums1)):\n",
    "            idx = bisect.bisect_left(a, nums2[i])\n",
    "            m = 0\n",
    "            if idx == 0:\n",
    "                m = abs(a[idx]-nums2[i])\n",
    "            elif idx == len(a):\n",
    "                m = abs(a[idx-1]-nums2[i])\n",
    "            else:\n",
    "                m = min(abs(a[idx-1]-nums2[i]), abs(a[idx]-nums2[i]))\n",
    "            tmp = min(tmp, s-abs(nums1[i]-nums2[i])+m)\n",
    "        return tmp % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        so = sorted(nums1)\n",
    "        total = 0\n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            diff = abs(nums1[i] - nums2[i])\n",
    "            total += diff\n",
    "            temp = bisect.bisect_left(so, nums2[i])\n",
    "            if temp > 0:\n",
    "                ans = min(ans, abs(so[temp - 1] - nums2[i]) - diff)\n",
    "            if temp < n:\n",
    "                ans = min(ans, abs(so[temp] - nums2[i]) - diff)\n",
    "        total = total % (10 ** 9 + 7)\n",
    "        return 0 if total == 0 else (total + ans) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n, total, sl, ans = len(nums1), 0, sorted(nums1), inf\n",
    "        for i in range(n):\n",
    "            diff = abs(nums1[i] - nums2[i])\n",
    "            total += diff\n",
    "            idx = bisect.bisect_left(sl, nums2[i])\n",
    "            # idx > 0 尝试用idx-1替换当前值\n",
    "            if idx:\n",
    "                ans = min(ans, abs(sl[idx-1] - nums2[i]) - diff)\n",
    "            # idx < n 尝试用idx替换当前值\n",
    "            if idx < n:\n",
    "                ans = min(ans, abs(sl[idx] - nums2[i]) - diff)\n",
    "        return (total + ans) % (10 ** 9 + 7) if total else total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int: \n",
    "        n=len(nums1)\n",
    "        q=sum(abs(nums1[i]-nums2[i]) for i in range(n))\n",
    "        if q==0:\n",
    "            return 0\n",
    "        f=sorted(nums1)\n",
    "        ans=inf\n",
    "        for i,x in enumerate(nums2):\n",
    "           ix=bisect.bisect_left(f,x)\n",
    "           if ix:\n",
    "               ans=min(ans,q-abs(nums1[i]-nums2[i])+abs(nums2[i]-f[ix-1]))\n",
    "           if ix<n:\n",
    "               ans=min(ans,q-abs(nums1[i]-nums2[i])+abs(f[ix]-nums2[i]))\n",
    "        return ans % (10**9+7)           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        sort = sorted(nums1)\n",
    "        s = 0\n",
    "        maxd = 0\n",
    "        for i in range(n):\n",
    "            x = abs(nums1[i] - nums2[i])\n",
    "            s += x\n",
    "            p = bisect_left(sort, nums2[i])\n",
    "            y = 1 << 30\n",
    "            if p > 0:\n",
    "                y = min(y, nums2[i] - sort[p - 1])\n",
    "            if p < n:\n",
    "                y = min(y, sort[p] - nums2[i])\n",
    "            # print(nums2[i], y)\n",
    "            maxd = max(maxd, x - y)\n",
    "        # print(s)\n",
    "        return (s - maxd) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        record = copy.deepcopy(nums1)\n",
    "        record.sort()\n",
    "        n = len(nums1)\n",
    "\n",
    "\n",
    "        maxChange = -1\n",
    "        ss = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            diff = abs(nums1[i] - nums2[i])\n",
    "            ss += diff\n",
    "            temp = self.helper(0, n - 1, record, nums2[i])\n",
    "            maxChange = max(maxChange, diff - temp)\n",
    " \n",
    "\n",
    "        ss -= maxChange\n",
    "\n",
    "        return ss%(10**9 + 7)\n",
    "        \n",
    "        \n",
    "    def helper(self, left, right, record, num):\n",
    "        n = right + 1\n",
    "        while left <= right:\n",
    "            mid = (right - left) // 2 + left\n",
    "            midV = record[mid]\n",
    "\n",
    "            if midV < num:\n",
    "                left = mid + 1\n",
    "            \n",
    "            elif midV > num:\n",
    "                right = mid - 1\n",
    "            \n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        if left <= n - 1 and right >= 0:\n",
    "            return min(abs(record[left] - num), abs(record[right] - num))\n",
    "\n",
    "        else:\n",
    "            if left <= n - 1:\n",
    "                return abs(record[left] - num)\n",
    "            else:\n",
    "                return abs(record[right] - num)\n",
    "        \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        abs_sum = 0\n",
    "        flag = 10**9+7\n",
    "        data_len = len(nums1)\n",
    "        for i in range(data_len):\n",
    "            abs_sum += abs(nums1[i]-nums2[i])\n",
    "            abs_sum %=flag\n",
    "        # nums1.sort()\n",
    "        new_nums1 = sorted(nums1)\n",
    "        ans = inf\n",
    "        def find(goal):\n",
    "            left = 0\n",
    "            right = data_len-1\n",
    "            while left<=right:\n",
    "                mid = left + (right-left)//2\n",
    "                if new_nums1[mid] == goal:\n",
    "                    return mid\n",
    "                elif new_nums1[mid] < goal:\n",
    "                    left= mid+1\n",
    "                else:\n",
    "                    right = mid-1\n",
    "            if right<0:\n",
    "                return 0\n",
    "            if left>data_len-1:\n",
    "                return data_len-1\n",
    "            if abs(new_nums1[left]-goal) <abs(new_nums1[right]-goal):\n",
    "                return left\n",
    "            else:\n",
    "                return right\n",
    "        # print(abs_sum)\n",
    "        # print(new_nums1)\n",
    "        for i in range(data_len):\n",
    "            index = find(nums2[i])\n",
    "            old = abs(nums1[i]-nums2[i])\n",
    "            new = abs(new_nums1[index]-nums2[i])\n",
    "            # print()\n",
    "            n_abs_sum = abs_sum-old+new\n",
    "            if n_abs_sum < ans:\n",
    "                # print(i,index,ans, n_abs_sum)\n",
    "                ans = n_abs_sum\n",
    "        # print(ans)\n",
    "        if ans <0:\n",
    "            # print(flag)\n",
    "            return flag + ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        tmp = nums1.copy()\n",
    "        tmp.sort()\n",
    "        s, maxdif = 0, 0\n",
    "        n = len(nums1)\n",
    "\n",
    "        def search(i):\n",
    "            l, r = 0, n-1\n",
    "            while l <= r:\n",
    "                m = (l+r)//2\n",
    "                if tmp[m] < nums2[i]:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m-1\n",
    "            return l # 找到左边界，大于等于nums2的\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums1[i] == nums2[i]: continue\n",
    "            x = abs(nums1[i]-nums2[i])\n",
    "            s += x\n",
    "            idx = search(i)\n",
    "            \n",
    "            if idx < n:\n",
    "                maxdif = max(maxdif, x-abs(tmp[idx]-nums2[i]))\n",
    "            if idx >=1:\n",
    "                maxdif = max(maxdif, x-abs(tmp[idx-1]-nums2[i]))\n",
    "\n",
    "        return (s-maxdif+1000000007) % 1000000007\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        diff = sum(abs(nums1[i] - nums2[i]) for i in range(n))\n",
    "        if diff == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        s1 = sorted(nums1)\n",
    "        for i, x in enumerate(nums2):\n",
    "            l = bisect_left(s1, x)\n",
    "            if l > 0:\n",
    "                ans = min(ans, diff - abs(nums1[i] - nums2[i]) + abs(s1[l - 1] - nums2[i]))\n",
    "            if l < n:\n",
    "                ans = min(ans, diff - abs(nums1[i] - nums2[i]) + abs(s1[l] - nums2[i]))\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        maxans = sum(abs(x-y)for x, y in zip(nums1, nums2))\n",
    "        ans = maxans\n",
    "        snums1 = sorted(nums1)\n",
    "        for i, num2 in enumerate(nums2):\n",
    "            a = bisect.bisect(snums1, num2)\n",
    "            if a < len(nums2):\n",
    "                ans = min(ans,maxans-abs(nums1[i]-nums2[i])+abs(snums1[a]-nums2[i]))\n",
    "            if a > 0:\n",
    "                ans = min(ans,maxans-abs(nums1[i]-nums2[i])+abs(snums1[a-1]-nums2[i]))\n",
    "        return ans%1000000007\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        lst = sorted(nums1)\n",
    "       \n",
    "        n = len(nums1)\n",
    "        s = sum(abs(nums1[i]-nums2[i]) for i in range(n))\n",
    "        ans = s\n",
    "        for i in  range(n):\n",
    "            cur = s - abs(nums1[i]-nums2[i])\n",
    "            j = bisect.bisect_left(lst, nums2[i])\n",
    "            for x in [j-1, j]:\n",
    "                if 0<=x<n and cur+abs(lst[x]-nums2[i]) < ans:\n",
    "                    ans = cur+abs(lst[x]-nums2[i])\n",
    "        return ans % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n, total, sl, ans = len(nums1), 0, sorted(nums1), inf\n",
    "        for i in range(n):\n",
    "            diff = abs(nums1[i] - nums2[i])\n",
    "            total += diff\n",
    "            idx = bisect.bisect_left(sl, nums2[i])\n",
    "            # idx > 0 尝试用idx-1替换当前值\n",
    "            if idx:\n",
    "                ans = min(ans, abs(sl[idx-1] - nums2[i]) - diff)\n",
    "            # idx < n 尝试用idx替换当前值\n",
    "            if idx < n:\n",
    "                ans = min(ans, abs(sl[idx] - nums2[i]) - diff)\n",
    "        return (total + ans) % (10 ** 9 + 7) if total else total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        abs_sum = 0\n",
    "        flag = 10**9+7\n",
    "        data_len = len(nums1)\n",
    "        for i in range(data_len):\n",
    "            abs_sum += abs(nums1[i]-nums2[i])\n",
    "            abs_sum %=flag\n",
    "        # nums1.sort()\n",
    "        new_nums1 = sorted(nums1)\n",
    "        ans = inf\n",
    "        def find(goal):\n",
    "            left = 0\n",
    "            right = data_len-1\n",
    "            while left<=right:\n",
    "                mid = left + (right-left)//2\n",
    "                if new_nums1[mid] == goal:\n",
    "                    return mid\n",
    "                elif new_nums1[mid] < goal:\n",
    "                    left= mid+1\n",
    "                else:\n",
    "                    right = mid-1\n",
    "            if right<0:\n",
    "                return 0\n",
    "            if left>data_len-1:\n",
    "                return data_len-1\n",
    "            if abs(new_nums1[left]-goal) <abs(new_nums1[right]-goal):\n",
    "                return left\n",
    "            else:\n",
    "                return right\n",
    "        # print(abs_sum)\n",
    "        # print(new_nums1)\n",
    "        for i in range(data_len):\n",
    "            index = find(nums2[i])\n",
    "            old = abs(nums1[i]-nums2[i])\n",
    "            new = abs(new_nums1[index]-nums2[i])\n",
    "            # print()\n",
    "            n_abs_sum = abs_sum-old+new\n",
    "            if n_abs_sum < ans:\n",
    "                # print(i,index,ans, n_abs_sum)\n",
    "                ans = n_abs_sum\n",
    "        # print(ans)\n",
    "        if ans <0:\n",
    "            # print(flag)\n",
    "            return flag + ans\n",
    "        return ans%flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n, total, sl, ans = len(nums1), 0, sorted(nums1), inf\n",
    "        for i in range(n):\n",
    "            diff = abs(nums1[i] - nums2[i])\n",
    "            total += diff\n",
    "            if diff + ans <= 0: continue\n",
    "            idx = bisect.bisect_left(sl, nums2[i])\n",
    "            # idx > 0 尝试用idx-1替换当前值\n",
    "            if idx:\n",
    "                ans = min(ans, abs(sl[idx-1] - nums2[i]) - diff)\n",
    "            # idx < n 尝试用idx替换当前值\n",
    "            if idx < n:\n",
    "                ans = min(ans, abs(sl[idx] - nums2[i]) - diff)\n",
    "        return (total + ans) % (10 ** 9 + 7) if total else total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        s = nums1.copy()\n",
    "        s.sort()\n",
    "        l = len(nums1)\n",
    "        ret, m = 0, 10 ** 9 + 7\n",
    "        r = 0\n",
    "        for a, b in zip(nums1, nums2):\n",
    "            t = abs(a - b)\n",
    "            ret += t\n",
    "            if t > r:\n",
    "                pl = min(l - 1, bisect.bisect_left(s, b))\n",
    "                na = s[pl]\n",
    "                # print(f\"find na {na} {s[pl - 1]} for {a}=>B {b}\")\n",
    "                nt = abs(na - b)\n",
    "                if pl - 1 >= 0:\n",
    "                    nt = min(nt, abs(s[pl - 1] - b))\n",
    "                r = max(r, t - nt)\n",
    "        # print(f\"ret {ret} {r}\")\n",
    "        return (ret - r) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        tmp = nums1.copy()\n",
    "        tmp.sort()\n",
    "        s, minx, maxdif = 0, pow(10, 9), 0\n",
    "        n = len(nums1)\n",
    "\n",
    "        def search(i):\n",
    "            l, r = 0, n-1\n",
    "            while l <= r:\n",
    "                m = (l+r)//2\n",
    "                if tmp[m] < nums2[i]:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m-1\n",
    "            return l # 找到左边界，大于等于nums2的\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums1[i] == nums2[i]: continue\n",
    "            x = abs(nums1[i]-nums2[i])\n",
    "            s += x\n",
    "            idx = search(i)\n",
    "            \n",
    "            if idx < n:\n",
    "                maxdif = max(maxdif, x-abs(tmp[idx]-nums2[i]))\n",
    "            if idx >=1:\n",
    "                maxdif = max(maxdif, x-abs(tmp[idx-1]-nums2[i]))\n",
    "\n",
    "        return (s-maxdif+1000000007) % 1000000007\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums1)\n",
    "        sort_nums1 = sorted(nums1)\n",
    "        f = [0] * n\n",
    "        for i, x in enumerate(nums2):\n",
    "            l = bisect_left(sort_nums1, x)\n",
    "            if l == n or (l > 0 and abs(sort_nums1[l - 1] - x) < abs(sort_nums1[l] - x)):\n",
    "                f[i] = abs(sort_nums1[l - 1] - x)\n",
    "            else:\n",
    "                f[i] = abs(sort_nums1[l] - x)\n",
    "        mx, p = -inf, 0\n",
    "        for i, x in enumerate(nums2):\n",
    "            if abs(nums1[i] - x) - f[i] > mx:\n",
    "                mx = abs(nums1[i] - x) - f[i]\n",
    "                p = i  \n",
    "        ans = 0\n",
    "        # print(f'mn:{mn},p:{p}')\n",
    "        for i, x in enumerate(nums2):\n",
    "            if i == p:\n",
    "                ans += f[i]\n",
    "            else:\n",
    "                ans += abs(nums1[i] - x)\n",
    "            ans %= mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        s = SortedList(nums1)\n",
    "        ans, res = 0, 0\n",
    "        for i in range(n):\n",
    "            t = abs(nums1[i] - nums2[i])\n",
    "            ans += t\n",
    "            ans %= kmod\n",
    "            idx = s.bisect_left(nums2[i])\n",
    "            for j in (idx - 1, idx):\n",
    "                if 0 <= j < n:\n",
    "                    res = max(res, t - abs(nums2[i] - s[j]))\n",
    "\n",
    "        return (ans - res) % kmod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        candidates = sorted(set(nums1))\n",
    "        n = len(candidates)\n",
    "        maxReduction = total = 0\n",
    "        for n1, n2 in zip(nums1, nums2):\n",
    "            thisVal = abs(n1 - n2)\n",
    "            total += thisVal\n",
    "            if thisVal <= maxReduction: continue\n",
    "            a = b = n1\n",
    "            idx = bisect_left(candidates, n2)\n",
    "            if idx: a = candidates[idx - 1]\n",
    "            if idx < n: b = candidates[idx]\n",
    "            value = va if (va := abs(a - n2)) <= (vb := abs(b - n2)) else vb\n",
    "            if (reduction := thisVal - value) > maxReduction:\n",
    "                maxReduction = reduction\n",
    "        return (total - maxReduction) % 1_000_000_007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        s = SortedList(nums1)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += abs(nums1[i] - nums2[i])\n",
    "            ans %= kmod\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            t = abs(nums1[i] - nums2[i])\n",
    "            idx = s.bisect_left(nums2[i])\n",
    "            for j in (idx - 1, idx):\n",
    "                if 0 <= j < n:\n",
    "                    v = abs(nums2[i] - s[j])\n",
    "                    res = max(res, t - v)\n",
    "\n",
    "        ans -= res\n",
    "        ans %= kmod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        tot = sum(abs(x-y) for (x,y) in zip(nums1,nums2))\n",
    "        a = [inf] + nums1.copy() + [inf]\n",
    "        a.sort()\n",
    "        max_diff = 0\n",
    "        n = len(nums1)\n",
    "        for x,y in zip(nums1,nums2):\n",
    "            l = 1\n",
    "            r = n\n",
    "            while l < r:\n",
    "                m = (l + r) >> 1\n",
    "                if a[m] < y:\n",
    "                    l = m + 1\n",
    "                else:\n",
    "                    r = m\n",
    "            t = min(abs(a[l] - y), abs(a[l-1] - y), abs(a[l+1] - y))\n",
    "            t = abs(x - y) - t\n",
    "            max_diff = max(max_diff,t)\n",
    "        return (tot - max_diff) % (10**9 + 7)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def upperbound(self,nums1,tar):\n",
    "        left = 0\n",
    "        right = len(nums1) - 1\n",
    "        while left <= right:\n",
    "            mid = int((left + right) /2 )\n",
    "            if nums1[mid] < tar:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid -1 \n",
    "            # print(\"uppper left \",left,\" right \",right)\n",
    "        if left == len(nums1):\n",
    "            return nums1[left - 1]\n",
    "        return nums1[left]\n",
    "    \n",
    "    def lowerbound(self,nums1,tar):\n",
    "        left = 0\n",
    "        right = len(nums1) - 1\n",
    "        while left <= right:\n",
    "            mid = int((left + right) / 2)\n",
    "            if nums1[mid] > tar:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "            # print(\"lower left \",left,\" right \",right)\n",
    "        if right == -1:\n",
    "            return nums1[0]\n",
    "        return nums1[right]\n",
    "\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums3 = sorted(nums1)\n",
    "        total = 0\n",
    "        n = len(nums1)\n",
    "        print(\"n \",n)\n",
    "        print(\"nums3 \",nums3)\n",
    "        for i in range(n):\n",
    "            total = total + abs(nums1[i] - nums2[i])\n",
    "            total = total % 1000000007\n",
    "        ans = total\n",
    "        sub = 0\n",
    "        for i in range(n):\n",
    "            up = self.upperbound(nums3,nums2[i])\n",
    "            low = self.lowerbound(nums3,nums2[i])\n",
    "            pre = abs(nums1[i] - nums2[i])\n",
    "            sub = max(sub,pre-abs(up - nums2[i]))\n",
    "            sub = max(sub,pre-abs(low - nums2[i]))\n",
    "        return (ans - sub) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        tot = 0\n",
    "        a = [inf] + nums1.copy() + [inf]\n",
    "        a.sort()\n",
    "        max_diff = 0\n",
    "        n = len(nums1)\n",
    "        for x,y in zip(nums1,nums2):\n",
    "            tot += abs(x-y)\n",
    "            l = 1\n",
    "            r = n\n",
    "            while l < r:\n",
    "                m = (l + r) >> 1\n",
    "                if a[m] < y:\n",
    "                    l = m + 1\n",
    "                else:\n",
    "                    r = m\n",
    "            t = abs(x - y) - min(abs(a[l] - y), abs(a[l-1] - y), abs(a[l+1] - y))\n",
    "            max_diff = max(max_diff,t)\n",
    "        return (tot - max_diff) % (10**9 + 7)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        res = list(abs(a - b) for a, b in zip(nums1, nums2))\n",
    "        ans = s = sum(res)\n",
    "        nums1.sort()\n",
    "        for i, gap in enumerate(res):\n",
    "            index = bisect_left(nums1, nums2[i])\n",
    "            if index: ans = min(ans, s - gap + abs(nums2[i] - nums1[index - 1]))\n",
    "            if index < len(res): ans = min(ans, s - gap + abs(nums2[i] - nums1[index]))\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n,res,ans,l=len(nums1),0,0,0\n",
    "        nums=sorted([(nums2[i],nums1[i]) for i in range(n)])\n",
    "        nums1.sort()\n",
    "        for i in nums:res+=abs(i[0]-i[1])\n",
    "        for i in nums:\n",
    "            while(l<n and nums1[l]<i[0]):l+=1\n",
    "            if(l):ans=max(ans,abs(i[0]-i[1])-(i[0]-nums1[l-1]))\n",
    "            if(l<n):ans=max(ans,abs(i[0]-i[1])-(nums1[l]-i[0]))\n",
    "        return (res-ans)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        nums = []\n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            total += abs(nums1[i]-nums2[i])\n",
    "            nums.append([nums1[i], nums2[i]])\n",
    "        nums.sort()\n",
    "        result = float('inf')\n",
    "        for i in range(n):\n",
    "            target = nums[i][1]\n",
    "            left, right = 0, n-1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(target <= nums[mid][0]):\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            if(left <= n-1 and right >= 0):\n",
    "                tmp = total - abs(nums[i][0]-nums[i][1]) + min(abs(nums[left][0]-nums[i][1]), abs(nums[right][0]-nums[i][1]))\n",
    "            elif(left <= n-1):\n",
    "                tmp = total - abs(nums[i][0]-nums[i][1]) + abs(nums[left][0]-nums[i][1])\n",
    "            else:\n",
    "                tmp = total - abs(nums[i][0]-nums[i][1]) + abs(nums[right][0]-nums[i][1])\n",
    "            result = min(result, tmp)\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        nums = []\n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            total += abs(nums1[i]-nums2[i])\n",
    "            nums.append([nums1[i], nums2[i]])\n",
    "        nums.sort()\n",
    "        result = float('inf')\n",
    "        for i in range(n):\n",
    "            target = nums[i][1]\n",
    "            left, right = 0, n-1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(target <= nums[mid][0]):\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            if(left <= n-1 and right >= 0):\n",
    "                tmp = total - abs(nums[i][0]-nums[i][1]) + min(abs(nums[left][0]-nums[i][1]), abs(nums[right][0]-nums[i][1]))\n",
    "            elif(left <= n-1):\n",
    "                tmp = total - abs(nums[i][0]-nums[i][1]) + abs(nums[left][0]-nums[i][1])\n",
    "            else:\n",
    "                tmp = total - abs(nums[i][0]-nums[i][1]) + abs(nums[right][0]-nums[i][1])\n",
    "            result = min(result, tmp)\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        nums = []\n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            total += abs(nums1[i]-nums2[i])\n",
    "            nums.append([nums1[i], nums2[i]])\n",
    "        nums.sort()\n",
    "        result = float('inf')\n",
    "        for i in range(n):\n",
    "            target = nums[i][1]\n",
    "            left, right = 0, n-1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(target <= nums[mid][0]):\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            if(left <= n-1 and right >= 0):\n",
    "                tmp = total - abs(nums[i][0]-nums[i][1]) + min(abs(nums[left][0]-nums[i][1]), abs(nums[right][0]-nums[i][1]))\n",
    "            elif(left <= n-1):\n",
    "                tmp = total - abs(nums[i][0]-nums[i][1]) + abs(nums[left][0]-nums[i][1])\n",
    "            else:\n",
    "                tmp = total - abs(nums[i][0]-nums[i][1]) + abs(nums[right][0]-nums[i][1])\n",
    "            result = min(result, tmp)\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        def binary_seek(num: List[int],item: int) -> int:\n",
    "            left,right = 0,len(num)-1\n",
    "            mid = left + (right - left)//2\n",
    "            while left < right:\n",
    "                if num[mid] > item:\n",
    "                    right = mid\n",
    "                elif num[mid] < item:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    break\n",
    "                mid = left + (right - left)//2\n",
    "            if mid == 0:\n",
    "                return min(abs(num[0]-item),abs(num[1]-item))\n",
    "            if mid == len(num)-1:\n",
    "                return min(abs(num[mid]-item),abs(num[mid-1]-item))\n",
    "            return min(abs(num[mid]-item),abs(num[mid-1]-item),abs(num[mid+1]-item))\n",
    "\n",
    "        l = len(nums1)\n",
    "        cha = [0]*l\n",
    "        Max = 0\n",
    "        Sum = 0\n",
    "        for i in range(l):\n",
    "            cha[i] = abs(nums1[i] - nums2[i])\n",
    "            Sum += cha[i]\n",
    "            Max = max(Max,cha[i])\n",
    "        if Max == 0:return 0\n",
    "\n",
    "        # 替换哪一个？  cha[i] 最大的那一个？\n",
    "        # 可替换的元素 nums1 中\n",
    "        \n",
    "        num = nums1.copy()\n",
    "        num.sort()\n",
    "\n",
    "        #change 记录 元素[i]交换后使cha[i]减少的最多值\n",
    "        change = [0]*l \n",
    "        Max = 0\n",
    "        for i in range(l):\n",
    "            #cha[i] 当前值\n",
    "            #在nums1中找（二分查找）离nums2[i]最接近的值\n",
    "            change[i] = cha[i] - binary_seek(num,nums2[i])\n",
    "            Max = max(Max,change[i])\n",
    "        return (Sum - Max)%(10**9+7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
